using array_demo.Model.Queue;

namespace array_demo.Model
{
    /// <summary>
    /// 二叉查找树  数据过多，树的高度过高() 排序数据容易导致层数过高
    /// </summary>
    /// <typeparam name="E"></typeparam>
    public class Bst1<E> where E : IComparable
    {

        private class Node
        {
            public E e;
            public Node left;
            public Node right;

            public Node(E e)
            {
                this.e = e;
                this.left = null;
                this.right = null;
            }

        }

        /// <summary>
        /// 根节点
        /// </summary>
        private Node root;

        /// <summary>
        /// 数据长度
        /// </summary>
        private int N;

        public Bst1()
        {
            root = null;
            N = 0;
        }

        public int Count { get { return N; } }

        public bool IsEmpty { get { return N == 0; } }

        /// <summary>
        /// 非递归添加
        /// </summary>
        public void Add(E e)
        {
            //判断根节点是否存在节点
            if (root == null)
            {
                root = new Node(e);
                N++;
                return;
            }

            Node pre = null;

            Node curr = root;

            while (curr != null)
            {
                if (e.CompareTo(curr.e) == 0)
                    return;

                pre = curr;

                if (e.CompareTo(curr.e) < 0)
                    curr = curr.left;
                else
                    curr = curr.right;
            }

            curr = new Node(e);

            if (e.CompareTo(pre.e) < 0)
                pre.left = curr;
            else
                pre.right = curr;

            N++;
        }

        /// <summary>
        /// 递归新增
        /// </summary>
        /// <param name="e"></param>
        public void AddV1(E e)
        {
            root = Add(root, e);
        }

        private Node Add(Node node, E e)
        {
            // 判断根节点为不为空
            if (node == null)
            {
                N++;
                return new Node(e);
            }

            // 判断插入的值和节点是否小于
            if (e.CompareTo(node.e) < 0)
            {
                node.left = Add(node.left, e);
            }
            else if (e.CompareTo(node.e) > 0)
            {
                node.right = Add(node.right, e);
            }
            return node;
        }

        public bool Contains(E e)
        {
            return Contains(root, e);
        }

        private bool Contains(Node node, E e)
        {
            if (node == null)
                return false;

            if (e.CompareTo(node.e) == 0)
                return true;

            else if (e.CompareTo(node.e) < 0)
                return Contains(node.left, e);
            else
                return Contains(node.right, e);
        }

        /// <summary>
        /// 前序遍历（深度遍历）
        /// </summary>
        public void PreOrd()
        {
            PreNode(root);
        }

        // 根 左  右
        private void PreNode(Node node)
        {
            if (node == null)
                return;

            Console.WriteLine($"前序遍历数据---{node.e}");

            PreNode(node.left);

            PreNode(node.right);
        }

        /// <summary>
        /// 中序遍历
        /// </summary>
        public void MidOrd()
        {
            MidNode(root);
        }

        // 左  根  右
        private void MidNode(Node node)
        {
            if (node == null)
                return;

            MidNode(node.left);

            Console.WriteLine($"中序遍历数据---{node.e}");

            MidNode(node.right);
        }

        /// <summary>
        /// 后序遍历
        /// </summary>
        public void PostOrd()
        {
            PostNode(root);
        }

        // 左  右  根 
        private void PostNode(Node node)
        {
            if (node == null)
                return;

            PostNode(node.left);

            PostNode(node.right);

            Console.WriteLine($"后序遍历数据---{node.e}");
        }

        /// <summary>
        /// 层序遍历
        /// </summary>
        public void LeverOrd()
        {
            Queue<Node> queue = new Queue<Node>();
            queue.Enqueue(root);
            while (queue.Count != 0)
            {
                Node curr = queue.Dequeue();
                Console.WriteLine(curr.e);
                if (curr.left != null)
                    queue.Enqueue(curr.left);
                if (curr.right != null)
                    queue.Enqueue(curr.right);
            }
        }

        public E Max()
        {
            if (IsEmpty)
                throw new ArgumentNullException("空树");
            return MaxNode(root).e;
        }

        private Node MaxNode(Node node)
        {
            if (node.right == null)
                return node;
            else
                return MaxNode(node.right);
        }

        public E Min()
        {
            if (IsEmpty)
                throw new ArgumentNullException("空树");
            return MinNode(root).e;
        }

        private Node MinNode(Node node)
        {
            if (node.left == null)
                return node;
            else
                return MaxNode(node.left);
        }

        public E DelMax()
        {
            E val = Max();
            root = RemoveMaxNode(root);
            return val;
        }

        public E DelMin()
        {
            E val = Min();
            root = RemoveMinNode(root);
            return val;
        }

        private Node RemoveMaxNode(Node node)
        {
            // 判断是不是最大值，或者右节点是否存在值
            if (node.right == null)
            {
                N--;
                // 如果没有就把左节点返回回去
                return node.left;
            }

            //  然后把节点的改成左节点的值
            node.right = RemoveMaxNode(node.right);

            return node;
        }

        private Node RemoveMinNode(Node node)
        {
            if (node.left == null)
            {
                N--;
                return node.right;
            }

            node.left = RemoveMinNode(node.left);

            return node;
        }

        public void Del(E e)
        {
            root = DelNode(root, e);
        }

        /// <summary>
        /// 删除树的任意元素
        /// </summary>
        /// <param name="node"></param>
        /// <returns></returns>
        private Node DelNode(Node node, E e)
        {
            if (node == null) return null;

            //查询元素
            if (e.CompareTo(node.e) < 0)
            {
                node.left = DelNode(node.left, e);
                return node;
            }
            else if (e.CompareTo(node.e) > 0)
            {
                node.right = DelNode(node.right, e);
                return node;
            }
            else
            {
                // 如果删除节点只存在右孩子节点
                if (node.left == null)
                {
                    N--;
                    return node.right;
                }

                // 如果删除节点只存在左孩子节点
                if (node.right == null)
                {
                    N--;
                    return node.left;
                }

                // 如果删除节点存在左右孩子节点
                // 找到比待删除节点大的最小节点，即删除节点右子树的最小节点
                // 用这个节点代替待删除的节点的位置

                // 先在右节点中查找一个最小值 
                Node s = MinNode(node.right);

                s.right= RemoveMinNode(node.right);
                s.left = node.left;
                return s;
            }
        }

        public int MaxHeight()
        {
            return MaxHeight(root);
        }

        private int MaxHeight(Node node)
        {
            if (node == null) return 0;
            // +1 node 本身节点高度
            return Math.Max(MaxHeight(node.left), MaxHeight(node.right)) + 1;
        }
    }
}